/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: LIUYANJIAO
 * Date: 2024-11-07
 * Time: 20:11
 */
public class Main {

    public static void swap(int[] arr,int a, int b){
        int tmp=arr[a];
       arr[a]=arr[b];
       arr[b]=tmp;
    }


    public static void shiftUp(int[] arr, int child){
        while(child>0){
            int parents=(child-1)/2;
            if(arr[parents]<arr[child]){
                swap(arr,parents,child);
                child=parents;
            }else {
                return;
            }
        }
    }
    public static int[] insert(int[] arr, int val){
        //返回一个新数组
        arr=java.util.Arrays.copyOf(arr,arr.length+1);
        arr[arr.length-1]=val;
        shiftUp(arr,arr.length-1);
        return arr;
    }
    public static int[] drop(int[] arr,int usesize){
        if(arr==null) return null;
        swap(arr,0,usesize-1);
        shiftDown(arr,0,usesize-2);
        return arr;
    }
//    public static int[] ascending(int[] arr){
//        int size=arr.length;
//        while(size>1){
//            swap(arr,0,size-1);
//
//            size--;
//            shiftDown(arr,0,size-1);
//
//        }
//        return arr;
//    }
public static void creat(int[] arr){
    for(int parents=(arr.length-2)/2;parents>=0;parents--){
        shiftDown(arr,parents,arr.length-1);
    }
}
public static int[] ascending(int[] arr){
    int size = arr.length;
    // 首先构建最大堆
    for (int i = (size - 2) / 2; i >= 0; i--) {
        shiftDown(arr, i, size - 1);
    }
    // 进行堆排序
    while (size > 1) {
        swap(arr, 0, size - 1); // 将最大值移到数组末尾
        size--; // 缩小堆的范围
        shiftDown(arr, 0, size - 1); // 重新调整堆
    }
    return arr;
}

    public static void shiftDown(int[] arr, int parents,int pos) {
        int largest = parents; // 记录最大值的下标
        int leftChild = 2 * parents + 1;
        int rightChild = 2 * parents + 2;

        // 比较父节点和左子节点
        if (leftChild <= pos && arr[leftChild] > arr[largest]) {
            largest = leftChild;
        }
        // 比较当前最大值和右子节点
        if (rightChild <= pos && arr[rightChild] > arr[largest]) {
            largest = rightChild;
        }

        // 如果最大值不是父节点，进行交换并递归调整
        if (largest != parents) {
            swap(arr, parents, largest);
            shiftDown(arr, largest, pos);
        }
    }



    public static void main(String[] args) {

        int[] arr= new int[]{22,56,2,21,5,28,32,0,5};
        ascending(arr);

    }
}